Various applications such as multimedia, digital libraries, virtual reality and information warehousing require the need for efficient storage and retrieval of objects in database. Objects are often provided in the form of video or image data, which may be detected utilizing various video or image-processing search and detection systems. Many technological advances could have been achieved in connection with such systems in recent years. Such systems and related methodologies, however, continue to still suffer from a slow response time due to the extensive processing required to analyze and search objects in video or image data formats, particularly in the context of image databases. Each object in such a database can be represented by a feature of the object. The feature can be a multidimensional data, which is typically in the form an appearance model of objects. Normally, such an appearance model is provided as an invariant representation of the objects in the database.
Moreover, an image database (e.g., including video database) typically supports the storage and retrieval of objects through the use of a simple linear search method. In a simple linear search method, the training data set is stored, and a distance function is calculated to determine which member of the training data is closest to a query data point. Once the nearest training data has been found, its class label can be predicted for the query data point. A simple linear search method exhibits a large search time, because the time for query one object is proportional to the number of objects stored in the training data set. If the image database possesses a large amount of data, the linear search time is large. So, the problem is the need for efficiently representing the training data set as a tree. A tree-based data structure represents the training data set in a tree. Thus, the search time for a query point on the tree-based data structure can approach O(log(n)) search times, which is faster than linear searches O(n) performed (e.g., in many cases dealing with a large database).
In the majority of prior art tree data structures, the procedure of the parent node splitting into the left child and the right child corresponds to the splitting of a region into two disjoint regions. Such disjoint regions can also overlap with each other in some cases. A technical difficulty encountered in most prior art tree data structures is that there is no mapping from the high-dimensional data into the low-dimensional data such that two objects, which are spatially close in the high-dimensional space, are still close in the low-dimensional space. Therefore, it is desirable to handle high-dimensional data with binary classification problem at less search time.
A need therefore exists for a method and system for building a support vector machine binary tree, which can handle high-dimensional data directly. Such an improved method and system is described in greater detail herein.